''' Created on Nov 15, 2009
# Problem Set 2 (Part III)
# Name: Noah Spahn
# Collaborators: none
# Time: 1:30'''

# http://olimu.com/Notes/ChickenNuggets.htm

'''Hypothesize possible instances of numbers of McNuggets that cannot be purchased 
   exactly, starting with 1
For each possible instance, called n,
      Test if there exists non-negative integers a, b, and c, such that
         6a+9b+20c = n. (This can be done by looking at all feasible
         combinations of a, b, and c)
      If not, n cannot be bought in exact quantity, save n
When you have found six consecutive values of n that in fact pass the test of
   having an exact solution, the last answer that was saved (not the last value
   of n that had a solution) is the correct answer, since you know by the
   theorem that any amount larger can also be bought in exact quantity'''
possible = []
notPossible = []

for n in range(1, 70):
    for c in (0,1,2):
        for b in (0,1):
            for a in range(0,40):
                if (6*a + 9*b + 20*c) == (n):
                    if n not in possible:
                        possible.append(n)
                        #print "adding to possible"
                elif n not in notPossible:
                        notPossible.append(n)
                        #print "adding to Not possible"
print "not Possible",len(notPossible)
print "possible list",len(possible)
for l in possible:
    if l in notPossible:
        notPossible.remove(l)
        #print "removing possibilities"
print "new size for Not",len(notPossible)
print "Largest number of McNuggets that cannot be bought in exact quantity:", notPossible.pop()


#def checknum(n,t):
#    if n > t:
#        return 1
#    else:
#        return 0
#    
#t = (6,9,20)
#
#for n in range(1, 200):
#    print "testing n"
#    p = t[0]
#    r = n % p
#    # print r, p
#    if checknum(r, t[1]):
#        r = r % t[1]
#        print r, t[1]
#        if checknum(r,t[0]):
#            r = r % t[0]
#            if r > 0:
#                bestsofar = n
#print bestsofar